package com.xyhuo.leetcode.december;

import java.util.*;

/**
 * 组合总和
 * https://leetcode.cn/problems/combination-sum/
 *
 * @time 2023/12/13
 */
public class CombinationSum {

//    public static void main(String[] args) {
//        CombinationSum cs = new CombinationSum();
//        int[] candidates = {2, 3, 5};
//        cs.combinationSum(candidates, 8);
//    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Map<Integer, List<List<Integer>>> map = new HashMap<>();
        Set<Integer> set = new HashSet<>();
        for (int candidate : candidates) {
            set.add(candidate);
        }
        for (int i = 1; i <= target; i++) {
            List<List<Integer>> list = new ArrayList<>();
            map.put(i, list);

            if (set.contains(i)) {
                List<Integer> item = new ArrayList<>();
                item.add(i);
                list.add(item);
            }
            Set<String> existSet = new HashSet<>();

            for (int j = 1; j <= i / 2; j++) {
                if (!map.get(j).isEmpty() && !map.get(i - j).isEmpty()) {
                    List<List<Integer>> one = map.get(j);
                    List<List<Integer>> two = map.get(i - j);
                    for (List<Integer> oneItem : one) {
                        for (List<Integer> twoItem : two) {
                            List<Integer> tmp = new ArrayList<>();
                            tmp.addAll(oneItem);
                            tmp.addAll(twoItem);
                            tmp.sort(new Comparator<Integer>() {
                                @Override
                                public int compare(Integer o1, Integer o2) {
                                    return o1 - o2;
                                }
                            });
                            StringBuilder sb = new StringBuilder();
                            for (Integer item : tmp) {
                                sb.append(item);
                                sb.append("#");
                            }
                            if (existSet.contains(sb.toString())) {
                                continue;
                            }
                            existSet.add(sb.toString());
                            list.add(tmp);
                        }
                    }
                }
            }
        }
        return map.get(target);
    }
}
